package JavaShengSai;

import java.util.Scanner;

/**
 * 11. 互质
 * https://www.lanqiao.cn/problems/2360/learning/?page=1&first_category_id=1&tags=2020,%E7%9C%81%E8%B5%9B&tag_relation=intersection&sort=pass_rate&asc=0
 */
public class Main16 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        // 互质就是两个整数的最大公约数 为1的话，就说明互为质数
        int a = 1018;
        int count = 0;
        for(int i = 1;i <= 2020;i++) {
            int b = i;
            if(gcb(a,b) == 1) {
                // 互质
                count++;
            }
        }
        System.out.println(count);
        scan.close();
    }
    public static int gcb(int a,int b) {
        if(a % b == 0) {
            return b;
        }
        return gcb(b,a % b);
    }
}
